package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type MyNode struct {
	node    *TreeNode
	visited bool
}

type BSTIterator struct {
	stack []*MyNode
}

func Constructor(root *TreeNode) BSTIterator {
	return BSTIterator{
		stack: []*MyNode{
			{
				node:    root,
				visited: false,
			},
		},
	}
}

func (this *BSTIterator) Next() int {
	for len(this.stack) > 0 {
		top := this.stack[len(this.stack)-1]
		this.stack = this.stack[:len(this.stack)-1]
		if top.visited {
			return top.node.Val
		}
		if top.node.Right != nil {
			this.stack = append(this.stack,
				&MyNode{
					node: top.node.Right,
				})
		}
		this.stack = append(this.stack, &MyNode{
			node:    top.node,
			visited: true,
		})
		if top.node.Left != nil {
			this.stack = append(this.stack, &MyNode{
				node: top.node.Left,
			})
		}
	}
	return 0
}

func (this *BSTIterator) HasNext() bool {
	return len(this.stack) > 0
}

func main() {
	root := &TreeNode{
		Val: 7,
		Left: &TreeNode{
			Val: 3,
		},
		Right: &TreeNode{
			Val: 15,
			Left: &TreeNode{
				Val: 9,
			},
			Right: &TreeNode{
				Val: 20,
			},
		},
	}
	iter := Constructor(root)
	for iter.HasNext() {
		println(iter.Next())
	}
}
